1. Field of the Invention
The present invention generally relates to data pre-fetch control devices, and more particularly to a data pre-fetch control device which predicts data to be accessed next on the basis of history information concerning the address used when a central processing unit accesses a storage unit and which pre-fetches predicted data whereby the access time can be substantially reduced.
2. Description of the Prior Art
Nowadays, the processing speed of central processing units is quite different from that of main memory devices. Normally, the central processing units can operate several times as fast as the main memory devices. Of course, there are available storage elements operable at an access speed corresponding to the processing speed of central processing units. However, such storage elements are expensive, and are not suitable for constituting main memory devices required to store a large amount of information.
Assuming that a high-speed central processing unit is a consumer who utilizes data and a low-speed main memory device is a supplier who supplies the consumer with data, data may be in a short supply at the consumer side. In this case, the central processing unit wastes much time before data is received from the main memory device. Hence, the processing performance is degraded.
In order to reduce the data waiting time of the central processing unit, a high-speed buffer device is provided between the central processing unit and the main storage unit. Normally, such a buffer device has a storage capacity less than that of the main memory unit. The buffer device absorbs the difference between the processing speeds of the central processing unit and main memory unit. Generally, buffer devices as described above are called cache memories.
A data pre-fetch method is known as another technique designed to reduce the data waiting time. Two types of data pre-fetch methods are known, one of which employs branch prediction, and the other is not limited to branch prediction.
The branch-prediction-based data pre-fetch method predicts an instruction to be executed next after a branch instruction in order to prevent a disturbance of a pipeline for execution of the branch instruction. More particularly, the following prediction methods are known.
In the first prediction method, a branch history table is referred to by using, as a key, an address indicating a memory area in which a branch instruction is stored. Thereby, an instruction related to the branch destination is obtained and executed.
In the second prediction method, a branch history table is referred to by using, as a key, an address indicating a memory area in which a branch instruction is stored. Thereby, the address of the branch destination is predicted, and an instruction is pre-fetched using the above address.
In the third prediction method, a branch history table is referred to by using, as a key, an address indicating a memory area in which a branch instruction is stored. Thereby, it is predicted whether the branch instruction will branch, and the next instruction is pre-fetched based on the result of the above prediction.
In the fourth prediction method, a counter is associated with a branch instruction. The counter is incremented by 1 when a branch occurs, and decremented by 1 when a branch does not occur. Based on the establishment of branching/non-blanching with respect to the branch instruction, the next instruction is predicted and pre-fetched. Data pre-fetch which is not limited to the branch prediction is classified into the following (1) or (2).
(1) A constant a is added to the subject address A of loading, and data pre-fetch is carried out by using A+.alpha. as a pre-fetch address.
(2) The cache line next to the subject cache line of loading is used a pre-fetch address.
The above-mentioned data pre-fetch methods based on branch prediction pre-fetch data only when a branch instruction is executed, and are hence effective in a program in which branch instructions do not occur frequently. Further, the above pre-fetch methods are capable of pre-fetching only instructions to be executed next after branch instructions. In other words, data specified by an operand is not subject to pre-fetching. Hence, the conventional pre-fetch method can be used for only limited applications.
In the aforementioned data pre-fetch method which is not limited to branch prediction, data to be accessed is not related to the actual processing logic but is fixed, because data indicated by address (X+n) is pre-fetched. Hence, the prediction does not have a high probability of being correct.